import functools


class Solution:
    @functools.lru_cache(None)
    def leastOpsExpressTarget(self, x: int, target: int) -> int:
        # 处理x=1的情况
        if x == 1:
            return target - 1

        # target取值:1
        if target == 1:
            return 1

        # target取值:(1,x)
        if target < x:
            print(target, ":", min(2 * (x - target), 2 * target - 1))
            return min(2 * (x - target), 2 * target - 1)

        # target取值:[x,+∞)
        # 计算第一项的最优次数：now*x<target now*(x+1)>=target
        times = 0
        while pow(x, times + 1) <= target:
            times += 1

        # 如果正好得到结果，则直接返回
        if pow(x, times) == target:
            return times - 1

        # 策略1
        a1, b1 = divmod(target, pow(x, times))
        ans1 = a1 * (times - 1) + a1 + self.leastOpsExpressTarget(x, b1)

        # 策略2
        a2, b2 = divmod(pow(x, times + 1) - target, pow(x, times))
        ans2 = (times + 1) + 1 + a2 * times - 1 + self.leastOpsExpressTarget(x, b2)

        ans = min(ans1, ans2)

        # print(target, ":", ans, "(", times, ans1, [a1, b1], ans2, [a2, b2], ")")
        return ans


if __name__ == "__main__":
    print(Solution().leastOpsExpressTarget(3, 19))  # 5
    print(Solution().leastOpsExpressTarget(5, 501))  # 8
    print(Solution().leastOpsExpressTarget(100, 100000000))  # 3
